<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        // 1. 接雨水
        // 时间复杂度：O(n)
        // 空间复杂度：O(n)
        var trap = function(height) {
            let n = height.length
            let ans = 0
            // 求前缀和数组: 最左边到i的最大值->前缀的最大值
            let prefix_max = []
            prefix_max[0] = height[0]
            for (let i = 1; i < height.length; i++) {
                prefix_max[i] = Math.max(height[i], prefix_max[i - 1])
            }

            // 求后缀和数组: 最右边到i的最大值->后缀的最大值
            let suffix_max = new Array(n)
            // 注意这里是n-1
            suffix_max[n - 1] = height[n - 1]
            for (let i = n - 2; i >= 0; i--) {
                suffix_max[i] = Math.max(height[i], suffix_max[i + 1])
            }
            console.log(height, 'height');
            console.log(prefix_max, 'prefix_max');
            console.log(suffix_max, 'suffix_max');
            // 同时遍历前缀数组,后缀数组,height数组
            for (let i = 0; i < height.length; i++) {
                // 判断当前位置的前缀和后缀谁的值更小
                let min = Math.min(prefix_max[i], suffix_max[i])
                // 最小值减去柱子的高度，就是能够容纳雨水的数量
                ans += min - height[i]
            }
            return ans
        };
        console.log(trap([0,1,0,2,1,0,1,3,2,1,2,1]));
        // console.log(maxArea([4,2,0,3,2,5]));
    </script>
</body>
</html>